class Solution {
    //简易方法（不考虑大数问题）
public:
    vector<int> printNumbers(int n) {
        if(n <= 0)  return vector<int>(0,0);
        int nTen = (int)pow(10, n);  //n位十进制数最大值+1
        vector<int> num(nTen - 1);
        for(int i = 0; i < nTen - 1; ++i)  num[i] = i + 1;
        return num;
    }
};

class Solution {
    //用字符串解决大数问题
    //把问题转换成n个0~9的数字全排列问题
    //int& stoi(string &)字符串转int
public:
    vector<int> printNumbers(int n) {
        //字符串最大长度应为n+1，因为还需要末尾结束符'\0'
        if(n <= 0)  return vector<int>(0,0);

        vector<int> numberOfPrint;
        string s = "\0";
        //需进行n轮排列，从s[0]到s[n - 1]
        for(int i = 0; i < 10; ++i){
            s[0] = '0' + i;
            dfs(numberOfPrint, s, n, 0);
        }
        
        return numberOfPrint;
    }

    //递归结束条件：已设置了最后一位
    void dfs(vector<int> &numberOfPrint, string &sNow, int &nLenght, int index){
        //nlenght表示字符串长度，index表示当前下标
        if(index >= nLenght - 1){
            //0不输出
            int sToInt = stoi(sNow);
            if(sToInt)  numberOfPrint.push_back(sToInt);
            return;
        }

        for(int i = 0; i < 10; ++i){
            sNow[index + 1] = '0' + i;
            dfs(numberOfPrint, sNow, nLenght, index + 1);  //i + 1接着递归
        }
    }
};